package com.lw.leetcode.back.b;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * b
 * back
 * 78. 子集
 * 面试题 08.04. 幂集
 *
 * @author liw
 * @version 1.0
 * @date 2021/9/13 15:39
 */
public class Subsets {

    public static void main(String[] args) {
        Subsets test = new Subsets();

        // 果
        //[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3],[3],[1,3],[2,3],[1,2,3],[3,3],[1,3,3],[2,3,3],[1,2,3,3]]
        // [[1], [1, 3], [1, 3], [1, 3, 3], [1, 2], [1, 2, 3], [1, 2, 3], [1, 2, 3, 3], [2], [2, 3], [2, 3], [2, 3, 3], [3], [3, 3], [3]]
        int[] arr = {1, 2, 3, 3};
        List<List<Integer>> subsets = test.subsets(arr);

        System.out.println(subsets);
    }


    private List<List<Integer>> all = new ArrayList<>();
    private List<Integer> list = new ArrayList<>();
    private int length;
    private int[] nums;

    public List<List<Integer>> subsets(int[] nums) {
        this.nums = nums;
        this.length = nums.length;
        all.add(new ArrayList<>());
        for (int i = 0; i < length; i++) {
            list.add(nums[i]);
            all.add(new ArrayList<>(list));
            find(i + 1);
            list.remove(0);
        }
        return all;
    }

    private void find(int index) {
        if (index == length) {
            return;
        }
        find(index + 1);
        list.add(nums[index]);
        all.add(new ArrayList<>(list));
        find(index + 1);
        list.remove(list.size() - 1);
    }

}
